package com.mj.listen2._02_并查集;

/**
 * Quick Find
 */
public class UnionFind_QF extends UnionFind {

    public UnionFind_QF(int capacity) {
        super(capacity);
    }

    @Override
    public int find(int v) {
        rangeCheck(v);
        // 直接返回数组索引中对应的值，就是根节点的值
        return parents[v];
    }

    /**
     * 将v1所在集合的所有元素都嫁接到v2的父节点上:
     * 将v1的父节点，改为v2的父节点，同时把所有与v1父节点相同的节点的父节点也改为v2的父节点
     * v1    v2   union(v1,v2)
     * 0    4	     4
     * 1 2   3     0 1 2 3
     */
    @Override
    public void union(int v1, int v2) {
        // 找到v1所在的父节点
        int p1 = find(v1);
        int p2 = find(v2);

        if (p1 == p2) {
            // 本身v1和v2就是同一个集合
            return;
        }

        for (int i = 0; i < parents.length; i++) {
            if (parents[i] == p1) {
                // 把所有与v1父节点相同的节点的父节点也改为v2的父节点
                parents[i] = p2;
            }
        }
    }
}
